<?php
// +----------------------------------------------------------------------
// | ThinkPHP
// +----------------------------------------------------------------------
// | Copyright (c) 2008 http://thinkphp.cn All rights reserved.
// +----------------------------------------------------------------------
// | Licensed ( http://www.apache.org/licenses/LICENSE-2.0 )
// +----------------------------------------------------------------------
// | Author: liu21st <liu21st@gmail.com>
// +----------------------------------------------------------------------
// $Id$

/**
 +------------------------------------------------------------------------------
 * ThinkPHP Tree实现类
 +------------------------------------------------------------------------------
 * @category   Think
 * @package  Think
 * @subpackage  Util
 * @author    liu21st <liu21st@gmail.com>
 * @version   $Id$
 +------------------------------------------------------------------------------
 */
class Tree extends Base {
	// 节点编号
	private $_id;
	// 节点等级
	private $_level;
	// 父节点
	private $_parent;
	// 子节点
	private $_child;
	// 节点数据
	private $data;

    /**
     +----------------------------------------------------------
     * 架构函数
     +----------------------------------------------------------
     * @access public
     +----------------------------------------------------------
     * @param array $data  初始化节点数据
     * @param mixed  $parent  父节点
     +----------------------------------------------------------
     */
    public function __construct($data=null,&$parent=null) {

        if ($parent===null){
            // 根节点
            $this->_level=0;
        }
        $this->data=$data;
        $this->_child=array();
        $this->_parent=&$_parent;
    }

    /**
     +----------------------------------------------------------
     * 添加子节点
     +----------------------------------------------------------
     * @access public
     +----------------------------------------------------------
     * @param mixed $data 节点数据
     +----------------------------------------------------------
     * @return Tree
     +----------------------------------------------------------
     */
    function &addChild($data) {
        $this->_child[] = new Tree($data,$this);
        end($this->_child);
        $key=key($this->_child);
        $this->_child[$key]->_setId($key);
        $this->_child[$key]->level = $this->_level + 1;
        return $this->_child[$key];
    }

    /**
     +----------------------------------------------------------
     * 移除子节点
     +----------------------------------------------------------
     * @access public
     +----------------------------------------------------------
     * @param integer $id 节点编号
     +----------------------------------------------------------
     * @return Boolean
     +----------------------------------------------------------
     */
    function removeChild($id) {
        if (!array_key_exists($id,$this->_child)){
            return false;
        }
        else{
            unset($this->_child[$id]);
            return true;
        }
    }

    /**
     +----------------------------------------------------------
     * 删除当前节点
     +----------------------------------------------------------
     * @access public
     +----------------------------------------------------------
     * @return Void
     +----------------------------------------------------------
     */
    function delete(){
        if (!$this->isRoot()){
            // remove using the _parent
            return $this->_parent->removeChild($this->_id);
        }
        else {
            // in the root node unset object
            unset ($this); //->_child=array();
            return true;
        }
    }

    /**
     +----------------------------------------------------------
     * 取得当前节点编号
     +----------------------------------------------------------
     * @access public
     +----------------------------------------------------------
     * @return integer
     +----------------------------------------------------------
     */
	function getId(){
		return $this->_id;
	}

    /**
     +----------------------------------------------------------
     * 设置当前节点编号
     +----------------------------------------------------------
     * @access public
     +----------------------------------------------------------
     * @param integer $id 节点编号
     +----------------------------------------------------------
     * @return void
     +----------------------------------------------------------
     */
	function _setId($id){
		 $this->_id=$id;
	}

    /**
     +----------------------------------------------------------
     * 取得子节点个数
     +----------------------------------------------------------
     * @access public
     +----------------------------------------------------------
     * @return Integer
     +----------------------------------------------------------
     */
	function numChild(){
		return count($this->_child);
	}

    /**
     +----------------------------------------------------------
     * 取得子节点的编号数组
     +----------------------------------------------------------
     * @access public
     +----------------------------------------------------------
     * @return Array
     +----------------------------------------------------------
     */
	function getChildIds(){
		return array_keys($this->_child);
	}

    /**
     +----------------------------------------------------------
     * 是否根节点
     +----------------------------------------------------------
     * @access public
     +----------------------------------------------------------
     * @return Boolean
     +----------------------------------------------------------
     */
    function isRoot(){
        if ($this->_parent==null){
            return true;
        }
        else{
            return false;
        }
    }

    /**
     +----------------------------------------------------------
     * 取得根节点
     +----------------------------------------------------------
     * @access public
     +----------------------------------------------------------
     * @return Tree
     +----------------------------------------------------------
     */
    function &getRoot(){
        $tmp=&$this;
        while (!$tmp->isRoot()){
            // iterate through parents, add IDs to (begin of) array
            $tmp=&$tmp->_parent;
        }
        return $tmp;
    }

    /**
     +----------------------------------------------------------
     * 取得当前节点路径
     +----------------------------------------------------------
     * @access public
     +----------------------------------------------------------
     * @return Array
     +----------------------------------------------------------
     */
    function getPath(){
        $idarray=array();
        $tmp=&$this;
        while (!$tmp->isRoot()){
            // iterate through parents, add IDs to (begin of) array
            array_unshift ($idarray, $tmp->_id);
            $tmp=&$tmp->_parent;
        }
        return $idarray;
	}

    /**
     +----------------------------------------------------------
     * 取得当前节点级别
     +----------------------------------------------------------
     * @access public
     +----------------------------------------------------------
     * @return Integer
     +----------------------------------------------------------
     */
    function getLevel(){
        $level=0;
        $tmp=&$this;
        while (!$tmp->isRoot()){
        //echo "adding level for parent, id :".$this->_id;
            $tmp=&$tmp->_parent;
            $level++;
        }
        return $level;
    }


    /**
     +----------------------------------------------------------
     * 输出结构
     +----------------------------------------------------------
     * @access public
     +----------------------------------------------------------
     * @param string $pre 节点数据
     +----------------------------------------------------------
     * @return void
     +----------------------------------------------------------
     */
    function echoStructure($pre='') {
        $str    =   '<pre>';
        for ($i=0;$i<$this->getLevel();$i++){
            $pre.='|';//$this->getLevel();
        }
        $str   .= $pre."+[".$this->_id.']';
        if (is_array($this->data)){
            foreach ($this->data as $key=>$value) {
                     $str .= '('.$key.'|'.$value.')';
            }
        }
        $str   .= "\n</pre>";
        if ($this->numChild()>0){
            foreach ($this->_child as $child) {
                $child->echoStructure($prefix);
            }
        }
        echo($str);
    }
}
?>